//
//  ProblemOffer16.swift
//  TestProject
//
//  Created by 武侠 on 2022/2/28.
//  Copyright © 2022 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 16. 数值的整数次方
 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

 示例 1：
     输入：x = 2.00000, n = 10
     输出：1024.00000
 示例 2：
     输入：x = 2.10000, n = 3
     输出：9.26100
 示例 3：
     输入：x = 2.00000, n = -2
     输出：0.25000
     解释：2-2 = 1/22 = 1/4 = 0.25
 提示：
     -100.0 < x < 100.0
     -231 <= n <= 231-1
     -104 <= xn <= 104
 */
class ProblemOffer16: NSObject {
    /*
     1: 将n转换成2的阶乘形式, 例如：6的二进制是110，转换成2的阶乘 2^0 * 0 + 2^1 * 1 + 2^2 * 2
     2: 那么n转换成阶层的形式：2^0 * b0 + 2^1 * b1 + ... + 2^(i-1) * b(i-1)， 其实bi是n转换成二进制每一位的值
     3: 对x^n进行转换：x^(2^0 * b0 + 2^1 * b1 + ... + 2^(i-1) * b(i-1))
     4: 分析一个通用项x^(2^(i-1) * b(i-1))
        b(i-1) == 0时，x^0 = 1
        b(i-1) == 1时，= x^(2^(i-1))
            f(i) = x^(2^i) = x^(2^i-1 * 2) = (x^(2^i-1))^2 = f(i-1)^2
            f(0) =  x
            f(1) = f(0)^2
      */
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 0
        }
        var xi: Double = x, sn = n
        var value: Double = 1
        if n < 0 {
            xi = 1 / x
            sn = -n
        }
        while sn > 0 {
            if sn & 1 == 1 {
                print("value = ", value, "*", xi, " = ", value * xi)
                value *= xi
            }
            print("xi = ", xi)
            xi *= xi
            
            sn >>= 1
        }
        
        return value
            
    }
}
